home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1998 April: Mac OS SDK / Dev.CD Apr 98 SDK1.toast / Development Kits (Disc 1) / QuickDraw 3D / Samples / SampleCode / Plug-in - DistanceProxyGroup / src / dpgSortedArray.c < prev    next >
Encoding:
C/C++ Source or Header  |  1997-08-14  |  3.8 KB  |  173 lines  |  [TEXT/MPS ]
  1. /******************************************************************************
  2.  **                                                                             **
  3.  **     Module:        dpgSortedArray.c                                         **
  4.  **                                                                          **
  5.  **                                                                          **
  6.  **     This is same as "Utility_SortedArray.c                                 **
  7.  **                                                                          **
  8.  **     Copyright (C) 1995-1996 Apple Computer, Inc.  All rights reserved.     **
  9.  **                                                                          **
  10.  **                                                                          **
  11.  *****************************************************************************/
  12.  
  13. #include "dpgMemory.h"
  14. #include "dpgSortedArray.h"
  15.  
  16. /******************************************************************************
  17.  **                                                                             **
  18.  **                                Array Macros                                 **
  19.  **                                                                             **
  20.  *****************************************************************************/
  21.  
  22. #define    EmArrayElement(a, elemSize, index)    \
  23.             ((char *) (a) + ((elemSize) * (index)))
  24.  
  25.  
  26. /******************************************************************************
  27.  **                                                                             **
  28.  **                                Array Maintenance                             **
  29.  **                                                                             **
  30.  *****************************************************************************/
  31.  
  32. /*===========================================================================*\
  33.  *
  34.  *    Routine:    dpgSortedArray_Search()
  35.  *
  36.  *    Comments:    
  37.  *
  38. \*===========================================================================*/
  39. TQ3Boolean dpgSortedArray_Search(
  40.     void                *key,
  41.     void                *array,
  42.     unsigned long        nElems,
  43.     unsigned long        elemSize,
  44.     dpgCompareFunction    compare,
  45.     unsigned long        *position)
  46. {
  47.     long    highElem    = nElems - 1;
  48.     long    midElem        = highElem / 2;
  49.     long    lowElem        = 0;
  50.     long    direction    = 1;
  51.     
  52.     while (    (highElem >= lowElem) &&
  53.             (direction = (*compare)(key, EmArrayElement(array, elemSize, midElem))) != 0)
  54.     {
  55.         if (direction > 0)
  56.         {
  57.             lowElem = midElem + 1;
  58.         }
  59.         else
  60.         {
  61.             highElem = midElem - 1;
  62.         }
  63.         midElem = (highElem + lowElem) / 2;
  64.     }
  65.     
  66.     if (direction == 0)
  67.     {
  68.         *position = midElem;
  69.         return kQ3True;
  70.     }
  71.     else
  72.     {    
  73.         *position = lowElem;
  74.         return kQ3False;
  75.     }
  76. }
  77.  
  78. /*===========================================================================*\
  79.  *
  80.  *    Routine:    dpgSortedArray_Resize()
  81.  *
  82.  *    Comments:    
  83.  *
  84. \*===========================================================================*/
  85. TQ3Status dpgSortedArray_Resize(
  86.     void                **array,
  87.     unsigned long        nElems,
  88.     unsigned long        elemSize)
  89. {
  90.     void    *newArray;
  91.         
  92.     if (nElems > 0)
  93.     {
  94.         newArray = dpgRealloc(*array, nElems * elemSize);
  95.         
  96.         if (newArray)
  97.         {
  98.             *array = newArray;
  99.             return (kQ3Success);
  100.         }
  101.     }
  102.     else
  103.     {
  104.         if (*array != NULL) {
  105.             dpgFree(*array);
  106.             *array = NULL;
  107.         }
  108.         return (kQ3Success);
  109.     }
  110.     
  111.     return (kQ3Failure);
  112. }
  113.  
  114. /*===========================================================================*\
  115.  *
  116.  *    Routine:    dpgSortedArray_Insert()
  117.  *
  118.  *    Comments:    
  119.  *
  120. \*===========================================================================*/
  121. void dpgSortedArray_InsertElement(
  122.     void                *array,
  123.     unsigned long        nElems,
  124.     unsigned long        elemSize,
  125.     void                *newElem,
  126.     unsigned long        position)
  127. {
  128.     
  129.     if (position < nElems)
  130.     {
  131.         dpgCopy(
  132.             EmArrayElement(array, elemSize, position),
  133.             EmArrayElement(array, elemSize, position + 1),
  134.             (nElems - position) * elemSize);
  135.     }
  136.     dpgCopy(
  137.         newElem,
  138.         EmArrayElement(array, elemSize, position),
  139.         elemSize);
  140. }
  141.  
  142. /*===========================================================================*\
  143.  *
  144.  *    Routine:    dpgSortedArray_DeleteElement()
  145.  *
  146.  *    Comments:    
  147.  *
  148. \*===========================================================================*/
  149. void dpgSortedArray_DeleteElement(
  150.     void                *array,
  151.     unsigned long        nElems,
  152.     unsigned long        elemSize,
  153.     void                *oldElem,    /* Can be NULL */
  154.     unsigned long        position)
  155. {
  156.     
  157.     if (oldElem)
  158.     {
  159.         dpgCopy(
  160.             EmArrayElement(array, elemSize, position),
  161.             oldElem,
  162.             elemSize);
  163.     }
  164.     if (position < nElems - 1)
  165.     {
  166.         dpgCopy(
  167.             EmArrayElement(array, elemSize, position + 1),
  168.             EmArrayElement(array, elemSize, position),
  169.             (nElems - position - 1) * elemSize);
  170.     }
  171. }
  172.  
  173.